#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAXSIZE 1000 // 树的最大结点数
typedef struct
{
    int nodes[MAXSIZE + 1]; // 存储结点值（0位置不使用）
    int n;                  // 当前结点个数
} SeqBinTree;

// 1. 初始树
void InitTree(SeqBinTree &T)
{
    for (int i = 0; i <= MAXSIZE; i++)
    {
        T.nodes[i] = 0; // 所有位置初始化为0（空结点）
    }
    T.n = 0; // 结点个数初始化为0
}

// 2. 销毁树
void DestroyTree(SeqBinTree &T)
{
    for (int i = 0; i <= MAXSIZE; i++)
    {
        T.nodes[i] = 0; // 清空所有结点
    }
    T.n = 0; // 结点个数归零
}

// 7. 判空树
bool TreeEmpty(SeqBinTree T)
{
    return (T.n == 0);
}

// 3. 插入结点
bool InsertNode(SeqBinTree &T, int value, int parent_index, bool isLeft)
{
    if (TreeEmpty(T))
    { // 树空时插入根结点
        if (parent_index != 0)
            return false; // 必须指定parent_index=0
        T.nodes[1] = value;
        T.n++;
        return true;
    }

    // 检查父结点有效性
    if (parent_index < 1 || parent_index > MAXSIZE || T.nodes[parent_index] == 0)
    {
        return false;
    }

    // 计算子结点位置
    int child_index = isLeft ? (2 * parent_index) : (2 * parent_index + 1);
    if (child_index > MAXSIZE)
        return false; // 越界检查
    if (T.nodes[child_index] != 0)
        return false; // 位置已被占用

    T.nodes[child_index] = value;
    T.n++;
    return true;
}

// 辅助函数：递归删除子树
void delete_subtree(SeqBinTree &T, int pos)
{
    if (pos < 1 || pos > MAXSIZE || T.nodes[pos] == 0)
        return;

    // 递归删除左右子树
    delete_subtree(T, 2 * pos);
    delete_subtree(T, 2 * pos + 1);

    // 删除当前结点
    T.nodes[pos] = 0;
    T.n--;
}

// 4. 删除结点
bool DeleteNode(SeqBinTree &T, int value)
{
    for (int i = 1; i <= MAXSIZE; i++)
    {
        if (T.nodes[i] == value)
        {
            delete_subtree(T, i); // 删除该结点及其子树
            return true;
        }
    }
    return false; // 未找到结点
}

// 前序遍历辅助函数
void preorder(SeqBinTree T, int pos)
{
    if (pos > MAXSIZE || T.nodes[pos] == 0)
        return;
    printf("%d ", T.nodes[pos]);
    preorder(T, 2 * pos);
    preorder(T, 2 * pos + 1);
}

// 中序遍历辅助函数
void inorder(SeqBinTree T, int pos)
{
    if (pos > MAXSIZE || T.nodes[pos] == 0)
        return;
    inorder(T, 2 * pos);
    printf("%d ", T.nodes[pos]);
    inorder(T, 2 * pos + 1);
}

// 后序遍历辅助函数
void postorder(SeqBinTree T, int pos)
{
    if (pos > MAXSIZE || T.nodes[pos] == 0)
        return;
    postorder(T, 2 * pos);
    postorder(T, 2 * pos + 1);
    printf("%d ", T.nodes[pos]);
}

// 层序遍历
void levelorder(SeqBinTree T)
{
    for (int i = 1; i <= MAXSIZE; i++)
    {
        if (T.nodes[i] != 0)
        {
            printf("%d ", T.nodes[i]);
        }
    }
}

// 5. 遍历树
void Traversal(SeqBinTree T, const char *order)
{
    if (strcmp(order, "preorder") == 0)
        preorder(T, 1);
    else if (strcmp(order, "inorder") == 0)
        inorder(T, 1);
    else if (strcmp(order, "postorder") == 0)
        postorder(T, 1);
    else if (strcmp(order, "levelorder") == 0)
        levelorder(T);
    printf("\n");
}

// 6. 查找结点
int Search(SeqBinTree T, int value)
{
    for (int i = 1; i <= MAXSIZE; i++)
    {
        if (T.nodes[i] == value)
        {
            return i; // 返回结点位置
        }
    }
    return 0; // 未找到
}

// 辅助函数：递归计算深度
int depth_recursive(SeqBinTree T, int pos)
{
    if (pos > MAXSIZE || T.nodes[pos] == 0)
        return 0;
    int left = depth_recursive(T, 2 * pos);
    int right = depth_recursive(T, 2 * pos + 1);
    return 1 + (left > right ? left : right);
}

// 8. 获取树深度
int TreeDepth(SeqBinTree T)
{
    return depth_recursive(T, 1);
}

int main()
{
    SeqBinTree T;
    InitTree(T);

    // 插入根结点
    InsertNode(T, 1, 0, true);
    printf("After inserting root node 1, is tree empty? %s\n", TreeEmpty(T) ? "Yes" : "No");

    // 插入其他结点
    InsertNode(T, 2, 1, true); // 1的左孩子
    InsertNode(T, 3, 1, false); // 1的右孩子
    InsertNode(T, 4, Search(T, 2), true); // 2的左孩子

    // 获取深度
    printf("Tree depth: %d\n", TreeDepth(T));

    // 遍历测试
    printf("Preorder traversal: ");
    Traversal(T, "preorder");

    printf("Inorder traversal: ");
    Traversal(T, "inorder");

    printf("Postorder traversal: ");
    Traversal(T, "postorder");

    printf("Levelorder traversal: ");
    Traversal(T, "levelorder");

    // 删除结点测试
    DeleteNode(T, 2);
    printf("After deleting node with value 2:\n");
    printf("Levelorder traversal: ");
    Traversal(T, "levelorder");

    printf("Tree depth: %d\n", TreeDepth(T));

    DestroyTree(T);
    return 0;
}